Лемма о степени вершины планарного графа

Любой плоский (планарный) граф можно раскрасить в 4 цвета

В любом обыкновенном планарном графе существует вершина степени $\leq 5$

Число ребер $m$ и число вершин $n$ обыкновенного планарного графа $G=(V,E)$ связаны неравенством $m \leq 3n-6$, которое является следствием из теоремы Эйлера о плоских графах. Тогда: $$\sum_{v \in V} \deg(v) = 2m \leq 6n - 12$$ Сумма $n$ слагаемых $\deg(v)$ меньше, чем $6n$, следовательно, найдется слагаемое, меньшее 6. $\square$